#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct no{char palavra[20]; unsigned short num; struct no *prox;} no;

void InserirNaLista(no **raiz, char palavra[20], short num){
    no *novo, *p;

    if((novo = (no*) malloc(sizeof(no))) == NULL){
        fprintf(stderr, "Falta de memoria");  
        exit(-1);
    }

    strcpy(novo->palavra, palavra);
    novo->prox = NULL;
    novo->num = num;
 
    if(*raiz == NULL) *raiz = novo;
    else{
        p = *raiz;

        while(p->prox != NULL)  p = p->prox;

        p->prox = novo;
    }
}

void RemoverDaLista(no **raiz){
    no* p = *raiz;
    *raiz = (*raiz)->prox;
    free(p);
}

no* ProcuraLista(no *raiz, char palavra[20]){
    no *p;
    
    for (p = raiz; p != NULL; p = p->prox) if (!strcmp(p->palavra, palavra)) return p;
    
    return NULL;
}

short ProcuraSimbolo(char palavra[50], short init, char simbolo){
    for (; palavra[init] != '\0'; ++init)
        if (palavra[init] == simbolo) return init;

    fprintf(stderr, "Nao foi encontrado o simbolo %c", simbolo);
    exit(-1);    
}

short ProcuraLabel(char linha[50], char palavra[20]){
    char *aux; //aux == possivel segundo delimitador de label
	short i, e, pos = 0; //pos == posição do ':' || e == corredor da linha || i == corredor da palavra

	if ((aux = strchr(linha, ':'))){//Se existir um delimitador de label na linha lida
		if (aux == strrchr(linha, ':')){//Se só existir um delimitador de label
			pos = aux-linha;
            
			for (i = e = 0; i < pos; ++i)
				if (linha[i] != ' ' && linha[i] != '\t') palavra[e++] = linha[i];//Copia o label
				
			palavra[e] = '\0';

        	++pos; //Ignora o ':'
            
			for (; linha[i] != '\0'; ++i)   linha[i-pos] = linha[i];//Retira o label da linha
			linha[i-pos] = '\0';
            
            return 1;
		}
		else {//ERRO: Se existir mais de um delimitador delabel na linha
			fprintf(stderr, "Nao e possivel ter mais de um label na mesma linha");
			exit(-1);				
		}
	}
    
    return 0;
    
}

short Registrador(short init, char linha[50]){

	if (linha[init] == '$'){//$--
		if (linha[init+1] == 't'){//$t-,
			if (linha[init+2] >= '0' && linha[init+2] <= '7')//$t[0-7],
				return 8 + (short)(linha[init+2] - '0');
			else if (linha[init+2] == '8') return 24; //$t8,
			else if (linha[init+2] <= '9') return 25; //$t9
			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);
			}
		} 
		else if (linha[init+1] == 's'){//$s--
			if (linha[init+2] >= '0' && linha[init+2] <= '7')//$s[0-7],
				return 16 + (short)(linha[init+2] - '0');
			else if (linha[init+2] == 'p')//$sp
				return 29;
			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);
			}
		} 
		else if (linha[init+1] == 'z' && linha[init+2] == 'e' && linha[init+3] == 'r' && linha[init+4] == 'o') //$ZERO,
			return 0;
		else if (linha[init+1] == 'a'){//$a--
			if (linha[init+2] == 't') return 1; //$at
			else if (linha[init+2] >= '0' && linha[init+2] <= '7')//$a[0-3]
				return 4 + (short)(linha[init+2] - '0');
			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);
			}
		}
		else if (linha[init+1] == 'v'){ //$v-
			if (linha[init+2] == '0') return 2; //$v0
			else if (linha[init+2] == '1') return 3; //$v1
			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);
			}			
		}
		else if (linha[init+1] == 'k'){//$k-
			if (linha[init+2] == '0') return 26; //$k0
			else if (linha[init+2] == '1') return 27; //$k1
			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);
			}				
		}
		else if (linha[init+1] == 'g' && linha[init+2] == 'p') return 28; //$gp
		else if (linha[init+1] == 'f' && linha[init+2] == 'p') return 30; //$fp
		else if (linha[init+1] == 'r' && linha[init+2] == 'a') return 31; //$ra
		else {
			fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);		
		}		
	} 
	else {
		fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
		exit(-1);		
	}
}

void AritLogica(no** instrucoes, char linha[50], char acao[4], short inst){
	short i;

    InserirNaLista(instrucoes, acao, inst);

    i = ProcuraSimbolo(linha, 0, '$');
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, ',') + 1;
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, ',') + 1;
    InserirNaLista(instrucoes, acao, Registrador(i, linha));
}

void StoreLoad(no** instrucoes, char linha[50], char acao[4], short inst){
	short i, j, dez;
    unsigned short base = 0;

    InserirNaLista(instrucoes, acao, inst);

    i = ProcuraSimbolo(linha, 0, '$');
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, '(');

    for (j = i - 1, dez = 1; linha[j] != ','; --j, dez *= 10){
    	if (linha[j] >= '0' && linha[j] <= '9')
    		base += ((unsigned short)(linha[j] - '0')) * dez;
    	else{
    		fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);	
		}
    }

    if (base >= 65536){
    	fprintf(stderr, "O valor da base ultrapassou os limites de 16 bits");
		exit(-1);	    	
    }

    InserirNaLista(instrucoes, acao, base);

    InserirNaLista(instrucoes, acao, Registrador(i+1, linha));

    i = ProcuraSimbolo(linha, i, ')');
}

void MovBits(no** instrucoes, char linha[50], char acao[4], short inst){
	short i, dez, shift = 0;

    InserirNaLista(instrucoes, acao, inst);

    i = ProcuraSimbolo(linha, 0, '$');
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, ',') + 1;
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    for (i = strlen(linha) - 1, dez = 1; linha[i] != ','; --i, dez *= 10){
        if (linha[i] >= '0' && linha[i] <= '9')
    		shift += ((unsigned short)(linha[i] - '0')) * dez;
    	else{
    		fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);	
		}
    }
    
    if (shift >= 32){
    	fprintf(stderr, "O valor do shmat ultrapassou o limite de 32");
		exit(-1);	    	
    }

    InserirNaLista(instrucoes, acao, shift);
}

void AddImed(no** instrucoes, char linha[50], char acao[4], short inst){
	short i, dez, num = 0;

    InserirNaLista(instrucoes, acao, inst);

    i = ProcuraSimbolo(linha, 0, '$');
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, ',') + 1;
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    for (i = strlen(linha) - 1, dez = 1; linha[i] != ','; --i, dez *= 10){
        if (linha[i] >= '0' && linha[i] <= '9')
    		num += ((unsigned short)(linha[i] - '0')) * dez;
    	else{
    		fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);	
		}
    }
    
    if (num >= 65536){
    	fprintf(stderr, "O valor imediato ultrapassou os limites de 16 bits");
		exit(-1);	    	
    }

    InserirNaLista(instrucoes, acao, num);
}

void Compara(no** instrucoes, char linha[50], char acao[4], short inst){
	short i, j = 0;
	char label[30];

    InserirNaLista(instrucoes, acao, inst);

    i = ProcuraSimbolo(linha, 0, '$');
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    i = ProcuraSimbolo(linha, i, ',') + 1;
    InserirNaLista(instrucoes, acao, Registrador(i, linha));

    for (i = ProcuraSimbolo(linha, i, ',') + 1; linha[i] != '\0'; ++i)
    	label[j++] = linha[i];
    label[j] = '\0';

    InserirNaLista(instrucoes, label, 0);
}

void Jump(no** instrucoes, char linha[50], char acao[4], short inst){
	short i, j = 0;
	char label[30];	

	InserirNaLista(instrucoes, acao, inst);

	for (i = strlen(acao); linha[i] != '\0'; ++i)
    	label[j++] = linha[i];
    label[j] = '\0';

	InserirNaLista(instrucoes, label, 0);    
}

void Acao(no** instrucoes, char linha[50]){
	if (linha[0] == 'a' && linha[2] == 'd'){ //AdD-, AdDi-, AnD-
		if (linha[1] == 'd'){ //ADD-, ADDi-
			if (linha[3] == '$')//ADD$
				AritLogica(instrucoes, linha, "add", 32);

			else if (linha[3] == 'i' && linha[4] == '$')//ADDI$
				AddImed(instrucoes, linha, "addi", 8);

			else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);				
			}
		} else if (linha[1] == 'n' && linha[3] == '$')//AND$
			AritLogica(instrucoes, linha, "and", 36);

		else {
			fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);				
		}
	} 
	else if (linha[0] == 's'){//Sw-, Sll-, Slt-, Srl-, Sub-
		if (linha[1] == 'w' && linha[2] == '$')//SW$
			StoreLoad(instrucoes, linha, "sw", 43);

		else if (linha[3] == '$'){//Sll$, Slt$, Srl$
			if (linha[1] == 'u' && linha[2] == 'b')//SUB$
				AritLogica(instrucoes, linha, "sub", 34);

			else if (linha[1] == 'r' && linha[2] == 'l')//SRL$
				MovBits(instrucoes, linha, "srl", 2);

			else if (linha[1] == 'l'){//SLl$ SLt$
				if (linha[2] == 'l') //SLL$
					MovBits(instrucoes, linha, "sll", 0);

				else if (linha[2] == 't') //SLT$
					AritLogica(instrucoes, linha, "slt", 42);

				 else {
					fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
					exit(-1);				
				}
			} else {
				fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
				exit(-1);					
			}
		}
	}
	else if (linha[0] == 'l' && linha[1] == 'w' && linha[2] == '$')//LW$
		StoreLoad(instrucoes, linha, "lw", 35);

	else if (linha[0] == 'b' && linha[3] == '$'){//Beq$, Bne$
		if (linha[1] == 'e' && linha[2] == 'q')//BEQ$
			Compara(instrucoes, linha, "beq", 4);

		else if (linha[1] == 'n' && linha[2] == 'e')//BNE$
			Compara(instrucoes, linha, "bne", 5);

		else {
			fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
			exit(-1);					
		}
	}

	else if (linha[0] == 'o' && linha[1] == 'r' && linha[2] == '$')//OR$
		AritLogica(instrucoes, linha, "or", 37);

	else if (linha[0] == 'j'){//J- Jal- Jr-
		if (linha[1] == 'r' && linha[2] == '$'){//JR$
			InserirNaLista(instrucoes, "jr", 8);
			InserirNaLista(instrucoes, "jr", Registrador(2, linha));
			
		} else if (linha[1] == 'a' && linha[2] == 'l')//JAL
			Jump(instrucoes, linha, "jal", 3);

		else //J
			Jump(instrucoes, linha, "j", 2);
		
	}
	else{
		fprintf(stderr, "Foi encontrado um caracter estranho em %s", linha);
		exit(-1);		
	} 

}

long TraduzStoreLoad(no** instrucoes, short opcode){
    long codigo = 0;
    
    codigo |= (*instrucoes)->num << 16; //registrador-destino
    RemoverDaLista(instrucoes);

    codigo |= (*instrucoes)->num;
    RemoverDaLista(instrucoes);

    codigo |= (*instrucoes)->num << 21; //registrador-memoria
    RemoverDaLista(instrucoes);

    codigo |= opcode << 26;
    
    //printf("%ld", codigo);
    
    return codigo;
}

long TraduzAritLogica(no** instrucoes, short funct){
    long codigo = 0;

	codigo |= (*instrucoes)->num << 11; //destino
	RemoverDaLista(instrucoes);

	codigo |= (*instrucoes)->num << 21; //fonte1
	RemoverDaLista(instrucoes);

	codigo |= (*instrucoes)->num << 16; //fonte2
	RemoverDaLista(instrucoes);

	codigo |= funct; //funct

	return codigo;
}

long TraduzAddImed(no** instrucoes){
    long codigo = 536870912; //2^29 == 8 << 26 | opcode

	codigo |= (*instrucoes)->num << 16; //rt
	RemoverDaLista(instrucoes);

	codigo |= (*instrucoes)->num << 21; //rs
	RemoverDaLista(instrucoes);

	codigo |= (*instrucoes)->num; //imediato
	RemoverDaLista(instrucoes);

	return codigo;
}

long TraduzMovBits(no** instrucoes, short funct){
    long codigo = 0;
    
    codigo |= (*instrucoes)->num << 11; // registrador destino
    RemoverDaLista(instrucoes);

    //rf1 == rf2
    codigo |= (*instrucoes)->num << 21; // registrador fonte1
    codigo |= (*instrucoes)->num << 16; // registrador fonte2
    RemoverDaLista(instrucoes);

    codigo |= (*instrucoes)->num << 6; //shamt
    RemoverDaLista(instrucoes);

    codigo |= funct;//funct
    
    return codigo;
}

void PrintBinario(FILE *fp,long codigo){
    short i;

    for (i = 31; i >= 0; --i) fprintf(fp, "%d", ((codigo & (1 << i)) != 0));
    
}

long TraduzCompara(no** instrucoes, no* labels, short opcode, short pc){
	long codigo = 0;
	unsigned short num;
	no* p;

	codigo |= (*instrucoes)->num << 21; // rs
    RemoverDaLista(instrucoes);

    codigo |= (*instrucoes)->num << 16; // rt
    RemoverDaLista(instrucoes);

    if ((p = ProcuraLista(labels, (*instrucoes)->palavra)) != NULL){
    	num = p->num - pc;
    	codigo |= num;
    } else {
    	fprintf(stderr, "Nao foi encontrado uma referencia a label %s", (*instrucoes)->palavra);
		exit(-1);	
    }
    RemoverDaLista(instrucoes);

    codigo |= opcode << 26;

    return codigo;
}

long TraduzJump(no** instrucoes, no* labels, short opcode, short pc){
	long codigo = 0;
	unsigned short num;
	no* p;

	if ((p = ProcuraLista(labels, (*instrucoes)->palavra)) != NULL){
    	num = p->num - pc;
    	codigo |= num;
    } else {
    	fprintf(stderr, "Nao foi encontrado uma referencia a label %s", (*instrucoes)->palavra);
		exit(-1);	
    }
    RemoverDaLista(instrucoes);

    codigo |= opcode << 26;

    return codigo;	
}

void Traducao(FILE *fp, no** instrucoes, no* labels){
	char acao[5];
	short pc = 1;
	long codigo;
	
	while (*instrucoes != NULL){
		strcpy(acao, (*instrucoes)->palavra);
        codigo = 0;
        RemoverDaLista(instrucoes);
       
        if (!strcmp(acao, "addi"))
    		codigo = TraduzAddImed(instrucoes);
        
        else if (!strcmp(acao, "add"))
            codigo = TraduzAritLogica(instrucoes, 32);
        
        else if (!strcmp(acao, "and"))
            codigo = TraduzAritLogica(instrucoes, 36);
        
        else if (!strcmp(acao, "sw"))
            codigo = TraduzStoreLoad(instrucoes, 43);
            
        else if (!strcmp(acao, "or"))
            codigo = TraduzAritLogica(instrucoes, 37);    
        
        else if (!strcmp(acao, "sub"))
            codigo = TraduzAritLogica(instrucoes, 34);
            
        else if (!strcmp(acao, "slt"))
            codigo = TraduzAritLogica(instrucoes, 42);
            
        else if (!strcmp(acao, "lw"))
            codigo = TraduzStoreLoad(instrucoes, 35);
            
        else if (!strcmp(acao, "srl"))
            codigo = TraduzMovBits(instrucoes, 2);
        
        else if (!strcmp(acao, "sll"))
            codigo = TraduzMovBits(instrucoes, 0);
            
        else if (!strcmp(acao, "bne"))
        	codigo = TraduzCompara(instrucoes, labels, 5, pc);

        else if (!strcmp(acao, "beq"))
        	codigo = TraduzCompara(instrucoes, labels, 4, pc);

        else if (!strcmp(acao, "j"))
        	codigo = TraduzJump(instrucoes, labels, 2, pc);

        else if (!strcmp(acao, "jal"))
        	codigo = TraduzJump(instrucoes, labels, 3, pc);

        else {//jr
            codigo |= (*instrucoes)->num << 21;
			codigo |= 8; //funct
			RemoverDaLista(instrucoes);
        }
        
        ++pc;
        PrintBinario(fp, codigo);
        fprintf(fp, "\n");
	}
}

int main(int argc, char const *argv[]){

    no *labels = NULL, *instrucoes = NULL;
    FILE *fp;
	char linha[50], palavra[20];
    short i, e, pc = 0; // pc == Program Counter

	if (argc != 2){//ERRO: Se o usuário passar mais de um nome de arquivo ou não passar nenhum nome
		fprintf(stderr, "Nao foi passado o numero correto de argumentos para o programa");
		exit(-1);
	}

	if ((fp = fopen("input.txt", "r")) == NULL){//ERRO: Se o arquivo passado não existir ou não puder ser aberto
		fprintf(stderr, "Nao foi possivel abrir/nao existe o arquivo %s", argv[1]);
		exit(-1);
	}

	for (; fgets(linha, 50, fp) != NULL; ++pc){
        
        for (i = e = 0; linha[i] != '\0'; ++i) 
        	if (linha[i] != '\0' && linha[i] != ' ' && linha[i] != '\t' && linha[i] != '\n' && linha[i] != '\r') linha[e++] = linha[i];//Remove os espaços em branco da linha
        linha[e] = '\0';

		if (ProcuraLabel(linha, palavra)){
    	    if (ProcuraLista(labels, palavra) == NULL)//Se ele já não tiver documentado o label
                InserirNaLista(&labels, palavra, pc);
                
            else{//ERRO: Se ele tiver documentado o label
				fprintf(stderr, "Nao e possivel ter um mesmo label em mais de uma linha");
				exit(-1);	                	
            }
		}

		Acao(&instrucoes, linha);
	}

	fclose(fp);

	if ((fp = fopen("output.txt", "w")) == NULL){//ERRO: Se o arquivo passado não existir ou não puder ser aberto
		fprintf(stderr, "Nao foi possivel criar existe o arquivo %s", argv[1]);
		exit(-1);
	}
	
	Traducao(fp, &instrucoes, labels);
	
	fclose(fp);

	return 0;
}

